package gsw.tool.arithmetic;

import java.util.LinkedList;

import gsw.tool.common.Tool;
import gsw.tool.common.ToolShow;

/**
 * 棋牌游戏常用排序算法包括：链式基数排序、插入排序、希尔排序。
 */
public class ChessSort {

    public static void test() {
//        //测试链式基数排序
//        LinkedList<MaJiang> list = new LinkedList<MaJiang>();
//        list.add(new MaJiang(1, 2));
//        list.add(new MaJiang(3, 7));
//        list.add(new MaJiang(2, 3));
//        list.add(new MaJiang(2, 1));
//        list.add(new MaJiang(2, 5));
//        list.add(new MaJiang(1, 9));
//        list.add(new MaJiang(3, 6));
//        linkedRadixSort(list);
//        ToolShow.log(list.toString());

        //测试插入排序
        Integer[] arr = new Integer[]{12, 4, 7, 15, 3};
        insertSort(arr);
        ToolShow.printArr(arr);

        //测试希尔排序
        Integer[] arr2 = new Integer[]{12, 4, 7, 15, 3};
        shellSort(arr);
        ToolShow.printArr(arr);
    }

    /**
     * 链式基数排序
     * <p>
     * 基数排序（Radix sort）属于“分配式排序”（distribution sort），它根据数据元素的某一特征将这些元素分成m组，然后再根据另一特征对组中的元素进行排序，即将一组数据变成m组排好序的数据。基数排序法是属于稳定性的排序。
     * 链式基数排序是按数据元素特征的优先级排序的基数排序，先按低优先级的特征，将这些元素分成m组，然后按照一定的顺序将它们串联成一组数据；然后再按高优先级的特征进行分组和串联。这样排好序后，就变成按多特征排序的一组数据。
     * 链式基数排序用于棋牌游戏洗牌。
     * <p>
     * 这里以麻将的排序来说明
     *
     * @param list 麻将集合
     */
    public static void linkedRadixSort(LinkedList<MaJiang> list) {
        if (Tool.isEmpty(list)) {
            return;
        }

        //先按点数分组
        LinkedList<MaJiang>[] rankList = new LinkedList[9];
        for (int i = 0; i < rankList.length; i++) {
            rankList[i] = new LinkedList<MaJiang>();
        }
        //按点数添加数据
        while (list.size() > 0) {
            MaJiang mj = list.remove();
            rankList[mj.rank - 1].add(mj);
        }
        //合并分组
        for (int i = 0; i < rankList.length; i++) {
            list.addAll(rankList[i]);
        }

        // 再按花色分组
        rankList = new LinkedList[3];
        for (int i = 0; i < rankList.length; i++) {
            rankList[i] = new LinkedList<MaJiang>();
        }
        //按花色添加数据
        while (list.size() > 0) {
            MaJiang mj = list.remove();
            rankList[mj.suit - 1].add(mj);
        }
        //合并分组
        for (int i = 0; i < rankList.length; i++) {
            list.addAll(rankList[i]);
        }
    }

    /**
     * 插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
     * 插入排序适用于棋牌游戏的插牌。
     *
     * @param arr 要排序的数组
     */
    public static <E extends Comparable<E>> void insertSort(E[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        //从前往后排序，先把前面所有的元素排好序，然后把后面的元素插到前面拍好的队列中
        for (int i = 1; i < arr.length; i++) {
            E temp = arr[i];
            int j = i;
            //找到需要插入的位置
            while (j > 0 && temp.compareTo(arr[j - 1]) < 0) {
                //后移一位
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = temp;
        }
    }

    /**
     * 希尔排序(Shell'S Sort)是将整个有序序列分割成若干小的子序列分别进行插入排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
     * 排序过程：先取一个小于n的整数d1作为第一个增量(也叫步长)，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量  =1(  <  …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
     * 希尔排序适合数组大部分有序的情况。希尔排序的效率还跟它的增量有关，适合的增量为：1,4,10,100..
     *
     * @param arr 要排序的数组
     */
    public static <E extends Comparable<E>> void shellSort(E[] arr) {
        if (Tool.isEmpty(arr)) {
            return;
        }
        shellSort(arr, 4);
        shellSort(arr, 1);
    }

    /**
     * 按步长进行希尔排序
     *
     * @param arr  要排序的数组
     * @param step 步长
     */
    public static <E extends Comparable<E>> void shellSort(E[] arr, int step) {
        if (Tool.isEmpty(arr)) {
            return;
        }
        for (int m = 0; m < step; m++) {
            for (int i = m + step; i < arr.length; i += step) {
                E temp = arr[i];
                int j = i;
                //与上一个步长的数据比较
                while (j - step >= 0 && temp.compareTo(arr[j - step]) < 0) {
                    //后移一个步长位
                    arr[j] = arr[j - step];
                    j -= step;
                }
                arr[j] = temp;
            }
        }

    }

    /**
     * 麻将
     */
    public static class MaJiang {
        int suit;// 花色
        int rank;// 点数

        public MaJiang(int suit, int rank) {
            super();
            this.suit = suit;
            this.rank = rank;
        }

        @Override
        public String toString() {
            return rank + getSuit(suit);
        }

        /**
         * 获取花色的名称
         *
         * @param suit 花色的数值
         * @return 花色的名称
         */
        private String getSuit(int suit) {
            if (suit == 1) {
                return "万";
            } else if (suit == 2) {
                return "条";
            } else {
                return "饼";
            }
        }
    }
}
